Sorting of data has become an important part of computing due to the increased use of computers and correlating increase in the volume and complexity of the data to be sorted. Developments in sorting of data in a more accurate, efficient, and rapid manner has also become increasingly important. Sorting frequently comprises two major actions: generation of a number of runs and merging of those runs. Run generation is a process of accepting unordered data, partially ordered data, or data of which the order is unknown, and forming this data into groups of ordered or sequenced data. The data is often sorted in numerical order or lexicographical order, although other orders may be used. Merging is a process of combining the generated runs into larger runs until one run or one set of ordered data remains. With the large volumes of data compiled in storage devices, and accessed by computing devices throughout the world, it is often difficult to ensure that the sorting of these large volumes of data takes as little time as possible to complete, and consumes as few computing resources as possible.
Throughout the drawings, identical reference numbers designate similar, but not necessarily identical, elements.